package leetcode;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-12 17:04
 **/
public class LeetCode647 {
    //回文串的个数,至少有n个回文串,即单字符
    int count = 0;

    //中心扩展算法
    public int countSubstrings(String s) {
        //字符串长度
        int n = s.length();

        for (int i = 0; i < n; ++i) {
            expand(s, i, i);
            expand(s, i, i + 1);
        }
        return count;
    }

    void expand(String s, int start, int end) {
        while (start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) {
            ++count;
            start--;
            end++;
        }
    }

    //动态规划
    /*public int countSubstrings(String s) {
        //字符串长度
        int n = s.length();
        //回文串的个数,至少有n个回文串,即单字符
        int count = n;
        boolean[][] dp = new boolean[n][n];

        for (int i = 0; i < n; ++i) {
            dp[i][i] = true;
        }

        //l: 长度
        for (int l = 2; l <= n; ++l) {
            for (int i = 0; i + l <= n; ++i) {
                int j = i + l - 1;

                if (l < 3) {
                    dp[i][j] = s.charAt(i) == s.charAt(j);
                } else {
                    dp[i][j] = dp[i + 1][j - 1] && s.charAt(i) == s.charAt(j);
                }

                if (dp[i][j]) {
                    ++count;
                }
            }
        }

        return count;
    }*/

    public static void main(String[] args) {
        LeetCode647 code = new LeetCode647();
        System.out.println("code.countSubstrings(\"abc\") = " + code.countSubstrings("abc"));
    }
}
